package 二叉树.前序遍历.栈方法;


import java.util.ArrayList;
import java.util.Stack;

class TreeNode {
    int val ;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root==null){
            return new int[]{} ;  // 返回一个空数组
        }
        // 1.根节点入栈
        stack.push(root);
        //2.只要栈内不为空,就循环
        while (!stack.isEmpty()){
            //3.将栈顶元素弹栈, 并获取值
            TreeNode pop = stack.pop();
            list.add(pop.val);
            //4.如果该元素的右孩子不为null :  先将右孩子压栈, 因为 出栈顺序是: 根 , 左, 右.  所以 右孩子必须要比左孩子先入栈。
            if (pop.right!=null){
                stack.push(pop.right);
            }
            if (pop.left!=null){
                stack.push(pop.left);
            }
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i]=list.get(i);
        }
        return ints;
    }


}
